{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "33e54782",
   "metadata": {},
   "source": [
    "## 堆排序和优先级队列\n",
    "\n",
    "[堆的概念](https://geek-blogs.com/blog/heap-in-python/)\n",
    "\n",
    "堆是一种特殊的树形结构，它可以用数组表示。\n",
    "堆的每一个节点都是大于或等于其子节点的值（最大堆）；或者每一个节点都小于或等于其子节点的值（最小堆）。\n",
    "\n",
    "**1. 堆与二叉树之间的关系是什么？**\n",
    "堆通常用数组来表示，并且可以看作是一个完全二叉树。完全二叉树是一种特殊的二叉树，除了最后一层外，每一层的节点数都是满的，并且最后一层的节点都靠左排列。这种结构使得堆在存储和操作上更加高效。\n",
    "\n",
    "**2. 将数组转化为堆**\n",
    "对于同一个数组，它可能对应多个符合要求的堆结构。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d8374435",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 查找给定元素的父节点，左右孩子节点\n",
    "def parent(i):\n",
    "    return int((i + 1) / 2) - 1\n",
    "def left(i):\n",
    "    return 2 * (i + 1) - 1\n",
    "def right(i):\n",
    "    return 2 * (i + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "badaf49d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 15, 8, 9, 10, 3, 7, 1, 4, 2]\n",
      "[17, 15, 8, 9, 10, 3, 7, 1, 4, 2]\n"
     ]
    }
   ],
   "source": [
    "# ## 将数组转化为堆\n",
    "# def build_big_heap(A):\n",
    "#     if len(A) == 1:\n",
    "#         return A\n",
    "#     k = 1\n",
    "#     while k < len(A):\n",
    "#         i = k\n",
    "#         if parent(i) < 0:\n",
    "#             k += 1\n",
    "#         elif A[parent(i)] < A[i]:\n",
    "#             temp = A[parent[i]]\n",
    "#             A[parent[i]] = A[i]\n",
    "#             A[i] = temp\n",
    "#             i = parent[i]\n",
    "\n",
    "\n",
    "def build_big_heap(A):\n",
    "    if len(A) == 1:\n",
    "        return A\n",
    "    k = 1\n",
    "    while k < len(A):\n",
    "        i = k\n",
    "        while parent(i) >= 0:\n",
    "            if A[parent(i)] < A[i]:\n",
    "                temp = A[i]\n",
    "                A[i] = A[parent(i)]\n",
    "                A[parent(i)] = temp\n",
    "                i = parent(i)\n",
    "            else:\n",
    "                break\n",
    "        k += 1\n",
    "    return A\n",
    "\n",
    "A = [1, 3, 4, 2, 9, 7, 8, 10, 15, 17]\n",
    "heap_A = build_big_heap(A)\n",
    "print(heap_A)\n",
    "print(A)\n",
    "\n",
    "# 算法复杂度：O(n*lg(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "26d4b7dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 7, 8, 9, 10, 15, 17]\n"
     ]
    }
   ],
   "source": [
    "## 实现堆排序 \n",
    "def maxify_heap(heap, size):\n",
    "    parent = 0\n",
    "    while left(parent) < size or right(parent) < size:\n",
    "        max_val = heap[parent]\n",
    "        child = parent\n",
    "\n",
    "        if left(parent) < size and heap[left(parent)] > max_val:\n",
    "            max_val = heap[left(parent)]\n",
    "            child = left(parent)\n",
    "\n",
    "        if right(parent) < size and heap[right(parent)] > max_val:\n",
    "            max_val = heap[right(parent)]\n",
    "            child = right(parent)\n",
    "        if child == parent:\n",
    "            return\n",
    "        \n",
    "        temp = heap[parent]\n",
    "        heap[parent] = max_val\n",
    "        heap[child] = temp\n",
    "        parent = child\n",
    "\n",
    "def heap_sort(A):\n",
    "    A = build_big_heap(A)\n",
    "    heap_size = len(A)\n",
    "    while heap_size > 1:\n",
    "        temp = A[0]\n",
    "        A[0] = A[heap_size -1]\n",
    "        A[heap_size - 1] = temp\n",
    "        heap_size -= 1\n",
    "        maxify_heap(A, heap_size)\n",
    "    return A\n",
    "\n",
    "A = [1, 3, 4, 2, 9, 7, 8, 10, 15, 17]\n",
    "A = heap_sort(A)\n",
    "print(A)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6972e1ff",
   "metadata": {},
   "source": [
    "## 优先级队列\n",
    "优先级队列在满足堆排序的基础上支持以下几种操作：\n",
    "1. inster(heap, x)\n",
    "2. maximun(heap)\n",
    "3. extractMax(heap)\n",
    "4. increaseKey(heap, i, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "aaca6cfd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17\n",
      "[15, 10, 8, 9, 2, 3, 7, 1, 4]\n"
     ]
    }
   ],
   "source": [
    "## 返回堆的最大值\n",
    "def maximum(heap):\n",
    "    return heap[0]\n",
    "\n",
    "## 去除堆的最大值元素\n",
    "def extractMax(heap):\n",
    "    if len(heap) < 1:\n",
    "        raise Exception(\"heap underflow\")\n",
    "\n",
    "    m = heap[0]\n",
    "    heap[0] = heap[len(heap) - 1]\n",
    "    heap.pop(len(heap) - 1)\n",
    "    maxify_heap(heap, len(heap))\n",
    "    return m\n",
    "\n",
    "A = [1, 3, 4, 2, 9, 7, 8, 10, 15, 17]\n",
    "heap_A = build_big_heap(heap_A)\n",
    "m = extractMax(heap_A)\n",
    "print(m)\n",
    "print(heap_A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "282b372e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[18, 15, 17, 9, 10, 3, 7, 1, 4, 2]\n"
     ]
    }
   ],
   "source": [
    "## 增加给定元素的值\n",
    "def increaseKey(heap, i, k):\n",
    "    if k < heap[i]:\n",
    "        return \n",
    "    heap[i] = k\n",
    "    while i > 0 and heap[parent(i)] < heap[i]:\n",
    "        temp = heap[i]\n",
    "        heap[i] = heap[parent(i)]\n",
    "        heap[parent(i)] = temp\n",
    "        i = parent(i)\n",
    "    return heap\n",
    "\n",
    "A = [1, 3, 4, 2, 9, 7, 8, 10, 15, 17]\n",
    "heap_A = build_big_heap(A)\n",
    "A = increaseKey(heap_A, 2, 18)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "973c7a0f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 17, 8, 9, 15, 3, 7, 1, 4, 2, 10]\n"
     ]
    }
   ],
   "source": [
    "## 插入新的元素\n",
    "def insert(heap, x):\n",
    "    heap.append(x)\n",
    "    i = len(heap) - 1\n",
    "    while i > 0 and heap[parent(i)] < heap[i]:\n",
    "        temp = heap[parent(i)]\n",
    "        heap[parent(i)] = heap[i]\n",
    "        heap[i] = temp\n",
    "        i = parent(i)\n",
    "    return heap\n",
    "A = [1, 3, 4, 2, 9, 7, 8, 10, 15, 17]\n",
    "heap_A = build_big_heap(A) \n",
    "A = insert(heap_A, 17)\n",
    "print(A)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
